Climbing stairs [Matrix Exponentiation]

Time: O(LogN); Space: O(1); easy

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note:

  • Given n will be a positive integer.

Example 1:

Input: 2

Output: 2

Explanation:

  • There are two ways to climb to the top.

    1. 1 step + 1 step

    2. 2 steps

Example 2:

Input: 3

Output: 3

Explanation:

  • There are three ways to climb to the top.

    1. 1 step + 1 step + 1 step

    2. 1 step + 2 steps

    3. 2 steps + 1 step

Hints:

  1. To reach nth step, what could have been your previous steps? (Think about the step sizes)

[9]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        def matrix_mult(m1, m2):
            return [[sum(a * b for a, b in zip(m1_row, m2_col)) for m2_col in zip(*m2)] for m1_row in m1]

        def identity(size):
            size = range(size)
            return [[(i == j) * 1 for i in size] for j in size]

        def matrix_exp(m, pow):
            assert pow >= 0 and int(pow) == pow, "Only non-negative, integer powers allowed"
            accumulator = identity(len(m))
            for i in range(pow):
                accumulator = matrix_mult(accumulator, m)
            return accumulator

        def print_table(data):
            for row in data:
                print(' '.join('%-5s' % ('%s' % cell) for cell in row))

        T = [[1, 1],
             [1, 0]]

        m_exp = matrix_exp(T, n)            # n=2: m_exp=[[2, 1], [1, 1]]; n=3: m_exp[[3, 2], [2, 1]]
        res = matrix_mult([[1, 0]], m_exp)  # n=2: res=[[2, 1]]; n=3: res=[[2, 1]]; [[3, 2]]

        return res[0][0]

[10]:

s = Solution1()
n = 2
assert s.climbStairs(n) == 2
n = 3
assert s.climbStairs(n) == 3

[11]:

class Solution2(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        prev, current = 0, 1
        for i in range(n):
            prev, current = current, prev + current,
        return current

[12]:

s = Solution2()
n = 2
assert s.climbStairs(n) == 2
n = 3
assert s.climbStairs(n) == 3